#include <bits/stdc++.h>
using namespace std;
int MOD;
typedef long long ll;

inline void addM(ll &a, ll b) { (a += b) %= MOD; }
inline void mulM(ll &a, ll b) { (a *= b) %= MOD; }
template <typename T, int SZ = 1000000>
struct SegTree {
  T addv[SZ], mulv[SZ], sum[SZ];
  int qL, qR;
  T build(int o, int l, int r, T *A) {
    mulv[o] = 1, addv[o] = 0;
    if (l == r) return sum[o] = A[l];
    int m = l + (r - l) / 2;
    return sum[o] = (build(o * 2, l, m, A) + build(o * 2 + 1, m + 1, r, A));
  }
  T query(int o, int L, int R) {
    if (qL <= L && R <= qR) return sum[o];
    int m = L + (R - L) / 2;
    T ans = 0;
    pushdown(o, L, R);
    if (qL <= m) addM(ans, query(o * 2, L, m));
    if (qR > m) addM(ans, query(o * 2 + 1, m + 1, R));
    return ans;
  }
  void pushdown(int o, int L, int R) {
    int lc = 2 * o, rc = lc + 1, M = L + (R - L) / 2;
    ll &m = mulv[o], &a = addv[o];
    if (m != 1) {
      for (int son : {lc, rc}) {
        mulM(addv[son], m);
        mulM(sum[son], m);
        mulM(mulv[son], m);
      }
      m = 1;
    }
    if (a != 0) {
      addM(addv[lc], a);
      addM(addv[rc], a);
      addM(sum[lc], a * (M - L + 1) % MOD);
      addM(sum[rc], a * (R - M) % MOD);
      a = 0;
    }
  }

  void update(int o, int L, int R, int op, T v) {
    if (qL <= L && R <= qR) {
      if (op == 2)
        addM(addv[o], v), addM(sum[o], v * (R - L + 1) % MOD);
      else
        mulM(addv[o], v), mulM(sum[o], v), mulM(mulv[o], v);
    }
    int m = L + (R - L) / 2, lc = 2 * o, rc = 2 * o + 1;
    pushdown(o, L, R);
    if (qL <= m) update(2 * o, L, m, op, v);
    if (qR > m) update(2 * o + 1, m + 1, R, op, v);
    sum[o] = (sum[lc] + sum[rc]) % MOD;
  }
};
const int NN = 1e5 + 8;
SegTree<ll, NN * 3> tree;
ll A[NN];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int N, M;
  cin >> N >> M;
  for (int i = 1; i <= N; ++i) cin >> A[i], A[i] %= MOD;
  tree.build(1, 1, N, A);
  cin >> M;
  for (int i = 0, o, v; i < M; ++i) {
    cin >> o >> tree.qL >> tree.qR;
    if (o != 3)
      cin >> v, tree.update(1, 1, N, o, v);
    else
      cout << tree.query(1, 1, N) << endl;
  }
  return 0;
}
